class Solution {
 public:
  // 1. dp[i]表示拆分i能获得的最大乘积
  // 2. dp[i]= max{dp[i],max(dp[i-j]*j,j*i-j)}
  // 3. dp[2]=1
  // 4. i:2->n,j:1->i
  // 5. 检查dp数组
  int integerBreak(int n) {
    vector<int> dp(n + 1, 0);
    // 严格从dp[i]的定义来说，dp[0] dp[1] 就不应该初始化，也就是没有意义的数值。
    dp[2] = 1;
    int i, j;
    // 遍历顺序dp[2]从前往后推，且dp[0]、dp[1]没有意义
    for (i = 3; i <= n; i++) {
      for (j = 1; j < i - 1; j++) {
        dp[i] = max(dp[i], max(dp[i - j] * j, j * (i - j)));
      }
    }
    return dp[n];
  }
};
// 这道题要好好注意第3步和第4步；